之前寫到過分治法，它並不是單一個演算法，而是許多演算法設計的基礎。同理，貪婪演算法也是一種設計模式。這類演算法的作法是，在每一個階段選擇當前最佳解，並以此達到整個問題的最佳解。

舉例來說，如果現在有一個空間可以借人使用，我們希望在時間不衝突的情況下，借越多組人越好，收益越多。現在有這些想借的團體和他們提出的時間：

如果利用貪婪演算法來解決這個問題，它的想法就是希望每一段時間都最大程度的利用這個空間(局部最佳解)，這樣整天就可以最大程度的利用這個空間(整體最佳解)。以時間的利用來說，演算法的步驟可以是：

1. 第一段借給使用時段最早結束的社團。
2. 借給第一段之後最早結束的社團。

以這樣的做法，第一段借給最早結束的圍棋社，圍棋社後開始並最早結束的是花藝社，花藝社後最早結束的是機器人社。所以一天下來借給最多組人的安排就是圍棋社→花藝社→機器人社。

在一些問題中，貪婪演算法就是這麼輕鬆就可以找到解法。這種演算法有一些特性：

1. 貪婪演算法通常很簡單，(同個問題)可以容易設計出一種或多種貪婪演算法。
2. 要分析貪婪演算法的執行時間通常也不難。
3. 大部分貪婪演算法並非永遠正確，也就是碰到某些輸入時，無法得出預期的最佳解。而且就算一個貪婪演算法是正確的，也很難證明。

第三點可能讓人覺得，這麼簡單果然有詐！竟然並非永遠正確？！我們可以先用背包問題(knapsack problem)來看貪婪演算法可能不正確的例子。

背包問題

如果一間店裡有各種價值和重量的東西，我們有一個最多能裝三公斤的背包，想知道在不超過背包容量的情況下，如何裝進最有價值的物品組合。

用貪婪演算法的話，局部最佳解可以是每一次都裝入背包容納得下、最值錢的東西。

當店裡的物品是這樣時，可以靠貪婪演算法裝入裝得下又最值錢的物品A，透過局部最佳解也得到了整體最佳解。

可是當店裡的物品如下，用貪婪演算法會裝入物品A，可是物品B加物品C卻是更值錢的選擇。

從這個例子可以看出，有時候貪婪演算法無法得到最佳解，但可以得到還ok的解。

可是如果有那麼多快速又正確的演算法，為什麼還要用這種很可能得不到最佳解的演算法呢？下一回會寫到適合使用貪婪演算法的問題和情境。